package com.caoyanan.algorithm.question.zuoTraining.training003.class08;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 *
 * 先给出可整合数组的定义:如果一个数组在排序之后，每相邻两个数差的绝对值 都为 1， 则该数组为可整合数组。
 * 例如，[5,3,4,6,2]排序之后为[2,3,4,5,6]， 符合每相邻两个数差的绝对值 都为 1，所以这个数组为可整合数组。
 * 给定一个整型数组 arr，请返回其中最大可整合子数组的长度。
 * 例如， [5,5,3,2,6,4,3]的最大 可整合子数组为[5,3,2,6,4]，所以返回 5。
 * @author: caoyanan
 * @time: 2021/5/26 5:26 下午
 */
public class Question06_IntegrableArray {

    public static void main(String[] args) {

        //数组 [7, 8, 5, 7, 5, 10, 7, 5, 2, 2] 的最大可整合数组长度为 9 ,在内层循环，set.add(arr[j])忘了写  2. int j = i + answer => int j = i + 1 因为虽然不考虑更短的，但是把不合法的给放过去了
        int i2 = integrableArray(new int[]{7, 8, 5, 7, 5, 10, 7, 5, 2, 2});
        System.out.println("数组 [7, 8, 5, 7, 5, 10, 7, 5, 2, 2] 的最大可整合数组长度为 "+i2);
        // j - i + 1 写成了 j-1+1
        int i1 = integrableArray(new int[]{7, 1, 10, 6, 7, 2, 4, 10, 7, 3});
        System.out.println(i1);
        int count = 1000;
        for (int i = 0; i < count; i++) {
            int[] arr = LogarithmInputGenerator.getInstance().generateRandomArray(10, 10);
            int answer = integrableArray(arr);
            System.out.printf("数组 %s 的最大可整合数组长度为 %s \n",
                    Arrays.toString(arr), answer);
        }
    }

    private static int integrableArray(int[] arr) {

        if (arr == null || arr.length == 0) {
            return 0;
        }
        int answer = 1;
        for (int i = 0; i < arr.length; i++) {
            int min = arr[i];
            int max = arr[i];
            Set<Integer> set = new HashSet<>();
            set.add(arr[i]);
            for (int j = i + 1; j < arr.length; j++) {
                if (set.contains(arr[j])) {
                    break;
                }
                set.add(arr[j]);
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);
                if (max - min == j - i) {
                    answer = Math.max(answer, j - i + 1);
                }
            }
        }
        return answer;
    }
}
